class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        length_m = len(word1)
        length_n = len(word2)
        DP = [[0 for _ in range(length_n + 1)] for _ in range(1)]
        DP.append([i for i in range(length_n + 1)])
        for i in range(length_m):
            for j in range(length_n + 1):
                if j == 0:
                    DP[i % 2][j] = i + 1
                else:
                    if word1[i] == word2[j - 1]:
                        DP[i % 2][j] = DP[(i + 1) % 2][j - 1]
                    else:
                        DP[i % 2][j] = min(DP[(i + 1) % 2][j - 1], DP[i % 2][j - 1], DP[(i + 1) % 2][j]) + 1
        return DP[(length_m + 1) % 2][length_n]




data = Solution()
word1 = "intention"
word2 = "execution"
print(data.minDistance(word1, word2))
